#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>

/**
 * @param matrix D矩阵，路径价值
 * @param p P矩阵，就是i节点到j节点路径中，j的前一个节点
 * 
 */
void create_matrix(int** matrix,int **p,int vertex_num,int edge_num){
    int x,y,weight,edge_count=0;
    int i,j,k;
    for(i=0;i<vertex_num;++i){
        for(j=0;j<vertex_num;++j){
            matrix[i][j]=INT32_MAX;
            p[i][j]=j;
        }
    }
    while(edge_count<edge_num){
        
    }
}

/**
 * 看懂三重循环是关键
 * 在视频讲解中，每一轮次更新都对应一个矩阵编号，也就是n。
 * 所以按道理说可以申请一个三位数组，[n][x][y]，其中n是编号，[x][y]是矩阵
 * 但是因为每次更新只需要用到前一个状态，所以就不用把所有存储起来，用一个二维数组即可
 * 
 * @param matrix D矩阵，路径价值
 * @param p P矩阵，就是i节点到j节点路径中，j的前一个节点
 */
void floyd(int **matrix,int **p,int vertex_num){
    int n,x,y,temp=0;
    //D(-1)是原始状态，所以更新的时候，直接从n=0开始
    for(n=0;n<vertex_num;++n){//控制循环次数这里的n实际上就是D(-1),D(0),D(1)...对矩阵的标记，同样是跳板节点
        //下面是对D矩阵和P矩阵的更新，可以令n=0，来看执行过程
        for(x=0;x<vertex_num;++x){
            for(y=0;y<vertex_num;++y){
                //
                temp=(matrix[x][n]==INT32_MAX || matrix[n][y]==INT32_MAX)?INT32_MAX:(matrix[x][n]+matrix[n][y]);
                if(temp<matrix[x][y]){
                    matrix[x][y]=temp;
                    p[x][y]=n;
                }
            }
        }
    }
}

int main(void){
    int ver_num,edge_num,i;
    
    /**
     * @param matrix D矩阵，路径价值
     * @param p P矩阵，就是i节点到j节点路径中，j的前一个节点
     */
    int** matrix_d,**matrix_p;

    return 0;
}